package CH01数组结构.LeetCode单调队列;


import java.util.ArrayDeque;
import java.util.Deque;

public class LC1438 {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> queueMax = new ArrayDeque<>();
        Deque<Integer> queueMin = new ArrayDeque<>();
        int n = nums.length;
        int left = 0;
        int right = 0;
        int ret = 0;
        while (right < n) {
            while (!queueMax.isEmpty() && queueMax.peekLast() < nums[right]) {
                queueMax.pollLast();
            }
            while (!queueMin.isEmpty() && queueMin.peekLast() > nums[right]) {
                queueMin.pollLast();
            }
            queueMax.offerLast(nums[right]);
            queueMin.offerLast(nums[right]);
            while (!queueMax.isEmpty() && !queueMin.isEmpty() && queueMax.peekFirst() - queueMin.peekFirst() > limit) {
                if (nums[left] == queueMin.peekFirst()) {
                    queueMin.pollFirst();
                }
                if (nums[left] == queueMax.peekFirst()) {
                    queueMax.pollFirst();
                }
                left++;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
}